/*
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.
 */

package search_in_rotated_sorted_array

import "sort"

//查找nums中的下降点
//若元素数量少于1个或者一直是升序
//则返回len(nums)
func decent(nums []int) int {
	l := len(nums)
	for i := 1; i < l; i++ {
		if nums[i] < nums[i-1] {
			return i
		}
	}
	return l
}

func search(nums []int, target int) int {
	p := decent(nums)
	firsthalf := nums[0:p]
	laterhalf := nums[p:]
	i1 := sort.SearchInts(firsthalf, target)
	if i1 < p && nums[i1] == target {
		return i1
	}
	i2 := sort.SearchInts(laterhalf, target) + p
	if i2 < len(nums) && nums[i2] == target {
		return i2
	} else {
		return -1
	}
}
